package com.ztom.v2;

import java.util.PriorityQueue;

/**
 * @author ZhangTao
 */
public class Code76FindMedianOfDataStream {

    class MedianFinder {

        private final PriorityQueue<Integer> maxHeap;
        private final PriorityQueue<Integer> minHeap;

        public MedianFinder() {
            maxHeap = new PriorityQueue<>((a, b) -> b - a);
            minHeap = new PriorityQueue<>();
        }

        public void addNum(int num) {
            if (minHeap.size() != maxHeap.size()) {
                maxHeap.offer(num);
                minHeap.offer(maxHeap.poll());
            } else {
                minHeap.offer(num);
                maxHeap.offer(minHeap.poll());
            }
        }

        public double findMedian() {
            return minHeap.size() != maxHeap.size()
                    // 不相等是奇数
                    ? maxHeap.peek()
                    // 相等是偶数
                    : (maxHeap.peek() + minHeap.peek()) / 2.0;
        }
    }
}
